A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem

摘要

In this paper, an adaptive variable neighbourhood search (AVNS) algorithm that\udincorporates large neighbourhood search (LNS) as a diversification strategy is proposed\udand applied to the capacitated vehicle routing problem. The AVNS consists\udof two stages: a learning phase and a multi-level VNS with guided local search.\udThe adaptive aspect is integrated in the local search where a set of highly successful\udlocal searches is selected based on the intelligent selection mechanism. In\udaddition, the hybridisation of LNS with the AVNS enables the solution to escape\udfrom the local minimum effectively. To make the algorithm more competitive in\udterms of the computing time, a simple and flexible data structure and a neighbourhood\udreduction scheme are embedded. Finally, we adapt a new local search move\udand an effective removal strategy for the LNS. The proposed AVNS was tested\udon the benchmark data sets from the literature and produced very competitive\udresults.